/*
    用时：3CLK - 1分钟，89分钟

    well:
    1、我承认前2 CLK 我边放着电视剧；
    
    一个总结：
    事实上，这类简单的东西——编程题基本都是这样，纯粹算法，没有多线程，没有其他考虑。
    所有的核心就是算法。

    而这个，我犯的最大错误就是，我没有对len分情况考虑。

    这其实是一个典型的递归型问题，当然——如果我严格用递归程序去做的话，这个问题就会很简单。
    但是，我没有用递归做。

    仔细想想，就算我不用递归程序，只要用子程序.....
    其实跑不了的——我想到了那种思路，就是递归。

    老实说，如果不考虑栈和len的大小，这个题目用递归会非常直接非常简单
    我甚至可以在15分钟内写出来——下次试试

    但，如果不用递归的方式写，就是我现在的写法。
    老实说
    这个程序，我觉得未必可以通过测试——是的，后面我会写一个测试函数的
    主要，是那个条件我不知道写的对不对。

    递归与否，终止条件是这类问题最重要的地方。
    今天就到这里了，不要纠结。
    一天两小时，差不多的。
    明天再说。

    现在我考虑的是，把多版本，git ，代码
    甚至测试环境加上。

    2023.11.19
    2 CLKS - 4min+ 就完成了
*/
#include <stdlib.h>

int find1(char n,char *a,char len,char *nst);
int find2(char n,char *a,char len,char *nst);

int find(char n,char *a,char len,char *nst)
{
    find1(n,a,len,nst);
}

int find1(char n,char *a,char len,char *nst)
{
    char start,end,mid;
    char dir;

    if( (NULL == a) || (NULL == nst) )
        return 0;                               // *

    if(len <= 0)
        return 0;                               // * 异常如何返回*nst？包括返回值没说，所以*nst未定义

    if(1 == len)
    {
        if(n == a[0])
            goto succ;
        else
            goto fail;
    }

    if(2 == len)
    {
        if( (n == a[0]) || (n == a[1]) )
            goto succ;
        else
            goto fail;
    }

// ----------------------------------------------------------------------------
    start = 0;
    end = len - 1;
    mid = (start + end) / 2;

    if(a[0] < a[len - 1])
        dir = -1;
    else
        dir = 1;    

    do
    {
        if(n == a[mid])
            goto succ;
        else
        {
            if(-1 == dir)
            {
                if(n < a[mid])
                    end = mid;
                else
                    start = mid;
            }
            else if(1 == dir)
            {
                if(n < a[mid])
                    start = mid;
                else
                    end = mid;            
            }
        }

        mid = (start + end) / 2; 
    }while( (mid != start) && (mid != end) );
    
    goto fail;


succ:
    *nst = 1;               // 老实说，这个题目我有点怀疑*nst返回什么，只能看具体题目，但按照这个，那就是1
    return 1;

fail:
    *nst = 0;
    return 0;
}

// 2023.11.19 递归实现版本
// 最终发现压根不需要也不太好用递归实现，直接 非递归实现了
int find2(char n,char *a,char len,char *nst)
{
    char s_len;
    char start,mid,end;
    char dir;

    if( (NULL == a) || (NULL == nst))       // check : a nst NULL
        return 0;

    if(0 == len)                            // check : len ZERO just go
        return 0;

    if(a[0] == a[len - 1])      // 单独处理好了         实际，我是一个考虑很多细节的人，然而...so，不应责备自己不够小心意外情况，可能相反，反而...
    {
        if(n != a[0])
        {
            *nst = 0;                   // not found
            return 0;
        }
        else
        {
            *nst = 1;                   // found!
            return 1;
        }
    }
    else
    {
        if(a[0] < a[len - 1])
            dir = -1;
        else
            dir = 1;
    }

    s_len = len;
    start = 0;
    end = len - 1;

    while(1)
    {
        if(1 == s_len)
        {
            if(n == a[0])
            {
                *nst = 1;                  // found
                return 1;
            }
            else
            {
                *nst = 0;                   // not found
                return 0;                
            }
        }

        if(2 == s_len)
        {
            if( (n == a[0]) || (n == a[s_len - 1]) )
            {
                *nst = 1;                   // found
                return 1;
            }
            else
            {
                *nst = 0;                   // not found
                return 0;                
            }
        }

        // s_len > 2 
        mid = (start + end) / 2;
        if(n == a[mid])
        {
            *nst = 1;                   // found
            return 1;
        }
        else
        {
            // 分方向
            if(-1 == dir)
            {
                if(n < a[mid])
                    end = mid;               // 取前半段
                else
                    start = mid;               //
            }
            else
            {
                if(n < a[mid])
                    start = mid;               // 取后半段
                else
                    end = mid;               //                
            }
        }

        // 重新计算 s_len
        s_len = end - start + 1;
    }
}

#include <stdbool.h>
// test_find 函数

void test_find(char n,char *a,char len,int except)
{
    char result;
    char ret;
    int comeout;
    int i;

    printf("test find():");

    ret = find(n,a,len,&result);

    comeout = ( (1 == ret) && (1 == result) )?true:false;
    if(comeout == except)
        printf("SUCCESS.\n");
    else    
        printf("FAILED!\n");

    printf("search %d in array:\n",n);
    for(i = 0;i < len;i++)
    {
        printf("%d\t",a[i]);
        if( 0x0F == (i % 0x0F) )
            printf("|\n");
    }
    printf("\n");
}



// end of file ----------------------------------------------------------------
